package jianzhi_offer;

import java.util.PriorityQueue;
import java.util.Stack;

public class _31_把数组排成最小的数 {
    public static void main(String[] args) {
        _31_把数组排成最小的数 test = new _31_把数组排成最小的数();
        System.out.println(test.PrintMinNumber(new int[]{3, 32, 321}));
        System.out.println(test.PrintMinNumber(new int[]{3334,3,3333332}));
    }

    public String PrintMinNumber(int[] numbers) {
        if(numbers == null || numbers.length ==0) return "";
        //用优先队列构造最小堆  最小堆规则如下 认为大的被放在后面
        PriorityQueue<Integer> heap = new PriorityQueue<>(numbers.length, (o1, o2) -> compare(o1, o2));
        for (int i : numbers) {
            heap.offer(i);
        }
        StringBuilder sb = new StringBuilder();
        while (!heap.isEmpty()) {
            sb.append(heap.poll());
        }
        return sb.toString();
    }

    public int compare(Integer a, Integer b) {
        if (a == b) return 0;
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        while (a != 0) {
            stack1.add(a % 10);
            a /= 10;
        }
        while (b != 0) {
            stack2.add(b % 10);
            b /= 10;
        }
        int head1 = stack1.peek();
        int head2 = stack2.peek();
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            if (stack1.peek() != stack2.peek()) {
                return stack1.pop() - stack2.pop();
            }
            stack1.pop();
            stack2.pop();
        }
        if (stack1.isEmpty()) {
            while (!stack2.isEmpty()){
                int now = stack2.pop();
                if(now == head1) continue;
                else return Integer.compare(head1,now);
            }
        }
        else{
            while(!stack1.isEmpty()){
                int now = stack1.pop();
                if(now == head2) continue;
                else return Integer.compare(now,head2);
            }
        }
       return 0;
    }
}
